// https://www.lintcode.com/problem/jump-game-ii/description

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: An integer
     */
    int jump(vector<int> &A) {
        // 动态规划
        // int n = nums.size();
        // vector<int> rec(n, INT_MAX);
        // rec[0] = 0;
        // for (int i = 0; i < n; ++i) {
        //     if (rec[i] != INT_MAX) { //注意
        //         for (int j = 0; j <= nums[i]; ++j) {
        //             if (i + j < n) rec[i + j] = min(rec[i + j], rec[i] + 1);
        //         }
        //     }
        // }
        // return rec[n - 1];

        vector<int> steps(A.size(), INT_MAX);
        steps[0] = 0;
        for (int i = 1; i < A.size(); ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if (steps[j] != INT_MAX && j + A[j] >= i)
                {
                    steps[i] = min(steps[i], steps[j] + 1);
                }
            }
        }
        return steps[steps.size() - 1];
        
        // 贪心算法
        // if (A.size() <= 1)
        // {
        //     return 0;
        // }
        // int cnt = 1;
        // int furthest = A[0];
        // for (int i = 1; i < A.size(); ++i)
        // {
        //     if (furthest >= A.size() - 1)
        //     {
        //         break;
        //     }
        //     if (i <= furthest && i + A[i] > furthest)
        //     {
        //         furthest = i + A[i];
        //         cnt++; //错误，会被重复计数，e.g.,[2,2,3,4,2,1]
        //     }
        // }
        // return cnt;

        int jump(vector<int> &A) {
        int start = 0, end = 0, farthest = 0, cnt = 0;
        while (end < A.size() - 1) { // 需要改成按跳的次数来循环
            cnt++;
            for (int i = start; i <= end; ++i) {
                if (i + A[i] > farthest) farthest = i + A[i];
            }
            start = end + 1;
            end = farthest;
        }
        return cnt;
    }
};